#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//使用哈希实现学生管理系统

//学生信息结构体
typedef struct _Student{
    int id;
    char name[32];
    //其他信息省略
}stu_t;

//链表节点结构体
typedef struct _Node{
    stu_t *data;
    struct _Node *next;
}node_t;

#define HASH_TABLE_SIZE 26

//哈希表的结构体
typedef struct _Hash_table{
    int (*hash_func)(char *);
    node_t *table[HASH_TABLE_SIZE];
}hash_t;

//哈希函数
int get_index(char *name){
    return *name - 'a'; //这里 我根据首字母获取下标
    //这个哈希函数可以自己设计 如：
    //根据 前两个字母的平均值 获取下标
    //根据 (首字母+学号)%HASH_TABLE_SIZE 获取下标
    //....
}

//哈希表初始化
hash_t *create_and_init_hash(){
    hash_t *p = (hash_t *)malloc(sizeof(hash_t));
    if(NULL == p){
        return NULL;
    }
    p->hash_func = get_index;//指定哈希函数
    for(int i = 0; i < HASH_TABLE_SIZE; i++){
        p->table[i] = NULL;
    }
    return p;
}

//插入信息
int insert_hash_table(hash_t *my_table, stu_t msg){
    stu_t *q = (stu_t *)malloc(sizeof(stu_t));
    if(NULL == q){
        return -1;
    }
#if 1
    q->id = msg.id;
    strcpy(q->name, msg.name);
#else
    // 内存拷贝的函数
    // void *memcpy(void *dest, const void *src, size_t n);
    // 表示将 src 指向的空间中的内容 拷贝 n 个字节到 dest 指向的空间空
    memcpy(q, &msg, sizeof(stu_t));
#endif
    //创建新节点
    node_t *pnew = (node_t *)malloc(sizeof(node_t));
    if(NULL == pnew){
        return -1;
    }
    pnew->data = q;
    pnew->next = NULL;
    //把节点插入哈希表
    int index = my_table->hash_func(q->name);
    //采用尾插
    if(NULL == my_table->table[index]){
        my_table->table[index] = pnew;
    }else{
        node_t *ptemp = my_table->table[index];
        while(NULL != ptemp->next){
            ptemp = ptemp->next;
        }
        ptemp->next = pnew;
    }
    return 0;
}

//查找信息
int search_hash_table(hash_t *my_table, char *find_name){
    //获取下标
    int index = my_table->hash_func(find_name);
    //遍历链表
    node_t *ptemp = my_table->table[index];
    while(NULL != ptemp){
        if(!strcmp(find_name, ptemp->data->name)){
            printf("找到学生信息 : %d  %s\n", ptemp->data->id, ptemp->data->name);
            return 0;
        }
        ptemp = ptemp->next;
    }
    printf("查无此人\n");
    return 0;
}

int main(int argc, const char *argv[])
{
    //创建并初始化哈希表
    hash_t *my_table = create_and_init_hash();

    //向表中插入数据
    stu_t s1 = {1001, "zhangsan"};
    insert_hash_table(my_table, s1);
    stu_t s2 = {1002, "lisi"};
    insert_hash_table(my_table, s2);
    stu_t s3 = {1003, "abao"};
    insert_hash_table(my_table, s3);
    stu_t s4 = {1004, "zhaoyun"};
    insert_hash_table(my_table, s4);

    //查找
    char find_name[32] = {0};
    while(1){
        printf("请输入要查找的学员的姓名:");
        scanf("%s", find_name);
        search_hash_table(my_table, find_name);
    }

    return 0;
}